package com.future;

import java.util.Arrays;


/**
 * Description: 875. 爱吃香蕉的珂珂
 * <p>
 * 示例 1：
 * <p>
 * 输入：piles = [3,6,7,11], h = 8
 * 输出：4
 * 示例 2：
 * <p>
 * 输入：piles = [30,11,23,4,20], h = 5
 * 输出：30
 * 示例 3：
 * <p>
 * 输入：piles = [30,11,23,4,20], h = 6
 * 输出：23
 * <p>
 * 1 <= piles.length <= 104
 * piles.length <= h <= 109
 * 1 <= piles[i] <= 109
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/koko-eating-bananas
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2023/2/1 15:02
 */
public class Solution_875 {

    public static void main(String[] args) {
        int[] piles = {30, 62, 79, 11};
        int h = 8;
        piles = new int[]{3, 6, 7, 11};
        h = 8;
       /* piles = new int[]{30, 11, 23, 4, 20};
        h = 5;*/
        piles = new int[]{20, 312884470};
        h = 312884469;
        System.out.println(minEatingSpeed(piles, h));
    }

    /**
     * 用例没跑完
     * <p>
     * 思路：1、数组排序
     * 2、找到位置i
     * 2.1答案在位置[i-1,i]，二分继续查找
     * 2.2答案在位置[i-1,i]，二分继续查找
     *
     * @param piles
     * @param h
     * @return
     */
    public static int minEatingSpeed(int[] piles, int h) {
        int N = piles.length;
        Arrays.sort(piles);
        if (h == N) {
            // 香蕉堆数和保安多少小时后回来h相等
            return piles[N - 1];
        }
        /**
         * 二分查找找到对应下标
         *
         */
        Info m = binarySearch(piles, 0, N - 1, h);
        /**
         * 说明上限位置是m，那么答案就在[m-1,m]位置之间的值上
         * 继续二分找到最小值
         */
        return calcMinSpeed(piles, m, h);
    }

    private static int calcMinSpeed(int[] piles, Info info, int h) {
        int i = info.index;
        int useHours = info.useHour;
        if (useHours == h) {
            return piles[info.index];
        }
        if (useHours < h) {
            /**
             * 答案在[i-1,i]之间
             */
            return getMinSpeed(piles, i - 1 >= 0 ? piles[i - 1] : 0, piles[i], h);
        } else {
            /**
             * 说明i是下限，上限在i+1
             */
            return getMinSpeed(piles, piles[i], i + 1 < piles.length ? piles[i + 1] : (int) Math.pow(10, 9) + 1, h);
        }
    }

    private static int getMinSpeed(int[] piles, int l, int r, int h) {
        if (l >= r) {
            return l;
        }
        int m = ((l + r) >> 1);
        int userHours = 0;
        for (Integer num : piles) {
            userHours += Math.ceil((double) num / m);
        }
        if (userHours == h) {
            return m;
        }
        if (userHours > h) {
            return getMinSpeed(piles, m + 1, r, h);
        } else {
            return getMinSpeed(piles, l, m - 1, h);
        }
    }

    private static Info binarySearch(int[] piles, int l, int r, int h) {
        if (l >= r) {
            return new Info(l, calc(piles, l));
        }
        int m = ((l + r) >> 1);
        int userHours = calc(piles, m);
        if (userHours == h) {
            return new Info(m, h);
        }
        if (userHours > h) {
            /**
             * 说明速度还不够快
             * 继续往右
             */
            return binarySearch(piles, m + 1, r, h);
        } else {
            /**
             * 速度过快，可以适当减少
             */
            return binarySearch(piles, l, m - 1, h);
        }
    }

    private static int calc(int[] piles, int m) {
        int ave = piles[m];
        int useHour = m;
        for (int i = m; i < piles.length; i++) {
            useHour += (Math.ceil((double) piles[i] / ave));
        }
        return useHour;
    }

    private static class Info {
        int index;
        int useHour;

        public Info(int index, int userHour) {
            this.index = index;
            this.useHour = userHour;
        }
    }
}
